package lew.bing.exp.alg;

import java.util.Arrays;

/**
 * Created by 刘国兵 on 2018/8/28.
 */
public class KMS {

    // next算法
    public static int[] next(String pattern) {
        int[] next = new int[pattern.length()];
        // 循环计算出每个next的值
        char[] chars = pattern.toCharArray();
        next[0] = -1;
        int j = 0;
        int k = -1;
        while (j < next.length - 1) {

            if (k == -1 || chars[j] == chars[k]) {

                next[++j] = ++k;

            } else {

                k = next[k];
            }
        }
        return next;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(next("abcabcd")));
    }

}
